Định nghĩa Độ phức tạp truyền thông

Xét hàm số f {\displaystyle f} : X × {\displaystyle \times } Y → {\displaystyle \rightarrow } Z trong đó ta giả sử X = Y = { 0 , 1 } n {\displaystyle X=Y=\{0,1\}^{n}} và Z = { 0 , 1 } {\displaystyle Z=\{0,1\}} . Alice nhận được dữ liệu vào là một xâu n-bit x {\displaystyle x} ∈ {\displaystyle \in } X và Bob nhận được một xâu n-bit y {\displaystyle y} ∈ {\displaystyle \in } Y. Bằng cách gửi đi cho nhau mỗi lần 1 bit (theo một giao thức truyền thông nhất định), Alice và Bob muốn tính giá trị hàm f ( x , y ) {\displaystyle f(x,y)} sao cho khi thực hiện xong, ít nhất một trong hai người biết giá trị của hàm. Dễ thấy sau khi một trong hai người biết kết quả thì chỉ cần người đó gửi kết quả cho người kia (bằng 1 bit) thì cả hai người đều biết kết quả. Độ phức tạp truyền thông xấu nhất của hàm f, ký hiệu là D ( f ) {\displaystyle D(f)} , được định nghĩa là

D ( f ) = {\displaystyle D(f)=} số bit ít nhất Alice và Bob cần gửi trong trường hợp xấu nhất

Trong định nghĩa trên, nên xem f {\displaystyle f} là một ma trận A {\displaystyle A} (gọi là ma trận dữ liệu vào) trong đó mỗi hàng ứng với một giá trị x {\displaystyle x} ∈ {\displaystyle \in } X và mỗi cột ứng với một y {\displaystyle y} ∈ {\displaystyle \in } Y. Mỗi phần tử của ma trận dữ liệu vào A x , y = f ( x , y ) {\displaystyle A_{\mathrm {x,y} }=f(x,y)} . Ban đầu cả Alice và Bob đều có một bản sao của toàn bộ ma trận A (giả sử cả hai người đều biết hàm f {\displaystyle f} ). Khi đó, bài toán tính giá trị hàm số có thể xem là việc định vị giá trị cần tính trên ma trận. Bài toán này có thể giải được nếu Alice hoặc Bob biết cả x {\displaystyle x} và y {\displaystyle y} . Khi mới bắt đầu, bất kì một trong số 2 2 n {\displaystyle 2^{2n}} phần tử của ma trận đều có thể là giá trị cần tính. Sau đó sau mỗi lần một người gửi đi 1 bit cho người kia, một số hàng/cột bị loại đi và thu được một ma trận con của A.

Một tập hợp R ⊆ {\displaystyle \subseteq } X × {\displaystyle \times } Y được gọi là một hình chữ nhật (tổ hợp) nếu bất kì khi nào ( x 1 , y 1 ) {\displaystyle (x_{1},y_{1})} ∈ {\displaystyle \in } R và ( x 2 , y 2 ) {\displaystyle (x_{2},y_{2})} ∈ {\displaystyle \in } R thì ( x 1 , y 2 ) {\displaystyle (x_{1},y_{2})} ∈ {\displaystyle \in } R. Một cách tương đương, R là một ma trận con của A sao cho R = M × {\displaystyle \times } N trong đó M ⊆ {\displaystyle \subseteq } X và N ⊆ {\displaystyle \subseteq } Y. Xét thời điểm hai người đã trao đổi k {\displaystyle k} bit. Với một giá trị cố định h {\displaystyle h} ∈ {\displaystyle \in } { 0 , 1 } k {\displaystyle \{0,1\}^{k}} , định nghĩa

T h = { ( x , y ) : h {\displaystyle T_{\mathrm {h} }=\{(x,y):h} chính là k-bit được trao đổi khi dữ liệu vào là ( x , y ) {\displaystyle (x,y)} }

Khi đó, T h {\displaystyle T_{\mathrm {h} }} ⊆ {\displaystyle \subseteq } X × {\displaystyle \times } Y, và T h {\displaystyle T_{\mathrm {h} }} là một hình chữ nhật của A.

Dãy các bit được gửi đi giữa Alice và Bob được gọi là lịch sử thực hiện của giao thức. Có thể xem quá trình thực hiện giao thức là như sau. Ban đầu tập hợp giá trị có thể là toàn bộ ma trận A. Ở mỗi bước, sau khi một bit được gửi đi, hai người thu hẹp được tập hợp các giá trị có thể thành một hình chữ nhật con của tập hợp giá trị ở bước trước. Cuối cùng khi toàn tất giao thức, tùy thuộc vào hình chữ nhật ở bước cuối cùng mà Alice và Bob quyết định giá trị hàm số là bao nhiêu. Nếu giao thức luôn tính đúng thì tất cả các phần tử của hình chữ nhật sau bước cuối cùng phải bằng nhau và Alice và Bob quyết định được giá trị cần tính chính là giá trị đó.

Ví dụ hàm đẳng thức

Trong phần này, ta xét ví dụ trong đó Alice và Bob muốn xác định xem dữ liệu vào của họ có bằng nhau hay không. Nghĩa là ta muốn xác định xem x {\displaystyle x} có bằng y {\displaystyle y} . Có thể chứng minh bài toán tính hàm đẳng thức (ký hiệu là EQ) luôn đòi hỏi trao đổi n {\displaystyle n} bit trong trường hợp xấu nhất.Trước hết, xét ví dụ x {\displaystyle x} và y {\displaystyle y} có 3 bit. Hàm đẳng thức được mô tả bởi ma trận dưới đây.Các hàng ứng với các giá trị của x {\displaystyle x} , và các cột ứng với các giá trị của y {\displaystyle y} .

EQ000001010011100101110111
00010000000
00101000000
01000100000
01100010000
10000001000
10100000100
11000000010
11100000001

Theo ma trận trên, hàm chỉ nhận giá trị 1 khi x {\displaystyle x} bằng y {\displaystyle y} (các phần tử trên đường chéo chính). Có thể nhận thấy việc gửi đi 1 bit dữ liệu vào giảm số khả năng đi 2 lần. Chẳng hạn, nếu ta biết bit đầu tiên của y {\displaystyle y} là 1, thì chỉ cần xem xét một nửa số cột (trong đó y {\displaystyle y} bằng 100, 101, 110, hoặc 111).

Định lý: D ( E Q ) = n {\displaystyle D(EQ)=n} .
Chứng minh. Giả sử cho mục đích phản chứng D ( E Q ) ≤ n − 1 {\displaystyle D(EQ)\leq n-1} . Nghĩa là tồn tại hai bộ dữ liệu vào khác nhau ( x , x ) {\displaystyle (x,x)} và ( x ′ , x ′ ) {\displaystyle (x',x')} có cùng một lịch sử h {\displaystyle h} . Vì mỗi lịch sử luôn xác định một hình chữ nhật, và f ( x , x ) = f ( x ′ , x ′ ) = 1 {\displaystyle f(x,x)=f(x',x')=1} nên f ( x , x ′ ) = 1 {\displaystyle f(x,x')=1} . Theo giả thuyết x ≠ x ′ {\displaystyle x\neq x'} nên giá trị đúng của hàm đẳng thức phải là 0 (mâu thuẫn).

Một cách diễn đạt khác của chứng minh trên là nếu D ( E Q ) {\displaystyle D(EQ)} nhỏ hơn n {\displaystyle n} , ta luôn tìm được một hình chữ nhật trong ma trận EQ chứa nhiều hơn một ô trên đường chéo chính. Tất cả các ô trong hình chữ nhật đó đều phải bằng 1 thì Alice và Bob mới được phép tính ra giá trị 1. Tuy nhiên không tồn tại hình chữ nhật nào như vậy trong ma trận EQ.